/**
Name demangler and mangled-name based reflection facilities. Functions
defined in this module can be executed at compile time.

BUGS:

These compiler bugs must be fixed:
$(UL $(LI $(BUGZILLA 2774) - Functions-as-properties makes it
          impossible to get the .mangleof a function)
     $(LI $(BUGZILLA 3026) - Segfault with incomplete static array
          initializer)
     $(LI $(BUGZILLA 3029) - Bug in array value mangling rule)
     $(LI $(BUGZILLA 3034) - Template instance name wrongly mangled as
          LName)
     $(LI $(BUGZILLA 3043) - Template symbol arg cannot be demangled)
     $(LI $(BUGZILLA 3050) - Allow exception in CTFE (patch))
)
 */
module nonstd.demangle;

import std.stdint;

private import nonstd.string;
public  import nonstd.reflection;

// Merge overload sets
private
{
    alias nonstd.string    .toString toString;
    alias nonstd.reflection.toString toString;
}


//===================================================================//
// Internal utilities
//===================================================================//

/*
[internal] check whether fun(args) throws
 */
version (unittest)
private template throws(alias fun)
{
    bool throws(T...)(T args) nothrow
    {
        try
        {
            // To prevent optimization for pure function call.
            static typeof(fun(args)) invoke(T args)
            {
                return fun(args);
            }
            invoke(args);
            return false;
        }
        catch
        {
            return true;
        }
    }
}

unittest
{
    static void fun(int n) pure
    {
        if (n == 0)
            throw new Exception("zero");
    }
    static assert( throws!fun(0));
    static assert(!throws!fun(1));
}


/*
[workaround] (null).length blocks CTFE
 */
version (unittest)
private size_t length(T)(T[] arr) nothrow
{
    return arr ? arr.length : 0;
}


/*
Returns an integer of type size_t represented by the string s.
 */
private size_t toSize(string s) pure
{
    const u = toUint(s);
    if (u > size_t.max)
        throw new Exception("size overflow");
    return cast(size_t) u;
}

unittest
{
    static assert(toSize("0") == 0u);
    static assert(toSize("4294967295") == 4294967295u);

    static if (is(size_t == uint))
        static assert(throws!toSize("4294967296"));
}


/*
Is ch ASCII alpha?
 */
package bool isAsciiAlpha(char ch) pure nothrow
{
    return ('a' <= ch && ch <= 'z') ||
           ('A' <= ch && ch <= 'Z');
}


//===================================================================//
// Public interface
//===================================================================//

// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// std.demangle compatibile interface
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
If the given string $(D name) is a valid D mangled symbol or type
_name, returns a natural string representation of that _name;
otherwise just returns $(D name).

Example:
--------------------
// mangled function name
string fun = demangle("_D3std4math3sinFNaNbeZe");
assert(fun == "pure nothrow real std.math.sin(real)");

// mangled template instance name
string temp = demangle("3std10functional__T9binaryFunVAyaa3_612b62Z");
assert(temp == `std.functional.binaryFun!("a+b")`);

// mangled type name
string type = demangle("HAyai");
assert(type == "string[int]");

// not a valid D mangled name
string invalid = demangle("errno");
assert(invalid == "errno");
--------------------
 */
string demangle(string name) /+pure+/ nothrow
{
    try
    {
        if (isQualifiedName(name))
            return toString(finish!parseQualifiedName(name));

        if (isMangledName(name))
            return toString(finish!parseMangledName(name));

        if (isType(name))
            return toString(finish!parseType(name));
    }
    catch
    {
    }
    return name;
}

unittest
{
    enum s1 = demangle("3std6traits__T6UnqualTxiZ");
    static assert(s1 == "std.traits.Unqual!(const(int))");

    enum s2 = demangle("_D3std4math3sinFNaNbeZe");
    static assert(s2 == "pure nothrow real std.math.sin(real)");

    enum s3 = demangle("Aya");
    static assert(s3 == "string");

    enum s4 = demangle("errno");
    static assert(s4 == "errno");
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Demangle-based reflection
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Parses the given string $(D n) as a mangled symbol name and returns a
$(D Symbol) object representing the symbol.

Throws:
$(D Exception) if $(D n) is not a valid mangled symbol name.

Example:
--------------------
// pure nothrow real std.math.sin(real x)
Symbol sym = decodeName("_D3std4math3sinFNaNbeZe");

assert(sym.name == "sin");
assert(sym.type.kind == Type.Kind.FUNCTION);
assert(toString(sym.type.attributes) == "pure nothrow");

Symbol parent = sym.parent[0];
assert(toString(sym) == "std.math");
--------------------
 */
Symbol decodeName(string n) pure
{
    if (isQualifiedName(n))
        return finish!parseQualifiedName(n);

    if (isMangledName(n))
        return finish!parseMangledName(n);

    error("not a D mangled name", n);
    assert(0);
}

unittest
{
    enum sym1 = decodeName("3std6traits__T6UniqueTxiZ");
    static assert(toString(sym1) == "std.traits.Unique!(const(int))");

    enum sym2 = decodeName(
            "_D3std7windows8iunknown8IUnknown6AddRefMFZk");
    static assert(toString(sym2) ==
            "uint std.windows.iunknown.IUnknown.AddRef()");
    static assert(sym2.type[0].needThis);

    static assert(throws!decodeName("4testZ")); // garbage
    static assert(throws!decodeName("Aya")); // not a name
}


/***************************************
Parses the given string $(D n) as a mangled type name and returns a
$(D Type) object representing the type.

Throws:
$(D Exception) if $(D n) is not a valid mangled type name.

Example:
--------------------
// immutable(char)[] a.k.a. string
Type type = decodeType("Aya");

Type etype = type.next[0];
assert(etype.kind == Type.Kind.CHAR)
assert(etype.storage == StorageClass.IMMUTABLE);
--------------------
 */
Type decodeType(string n) pure
{
    return finish!parseType(n);
}

unittest
{
    enum dn1 = decodeType("G42ya");
    static assert(toString(dn1) == "immutable(char)[42]");

    static assert(throws!decodeType("AyaZ")); // garbage
    static assert(throws!decodeType("3std")); // not a type
}


//===================================================================//
// Core
//===================================================================//

/*
$(D Demangle) contains a mangled name and the information $(D Content)
extracted from the mangled name.
 */
private struct Demangle(Content)
{
    // The mangled name corresponding to the $(D content).
    string mangle;

    // The extracted information.
    Content content;
}


/*
Parses $(D man) as a complete syntax.

This function calls $(D parse(man)) and returns the $(D content) field
of the result. This function throws if there are garbages that has not
been parsed by $(D parse) at the end of $(D man).
 */
private auto finish(alias parse)(string man) pure
{
    auto dem = parse(man);
    if (dem.mangle.length != man.length)
    {
        const rem = man[dem.mangle.length .. $];
        error("garbage at the end of the input", rem);
    }
    return dem.content;
}


/*
Throws an exception with the error message $(D msg).

Params:
  msg = The error message.
  man = The mangled name closely related to the error.
 */
private void error(string msg, string man) pure
{
    throw new Exception(msg);
}


/*
Invokes $(D error(msg, man)) if $(D pred == false), or do nothing
otherwise.
 */
private void expect(bool pred, string msg, string man) pure
{
    if (!pred)
        error(msg, man);
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// General
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Parses the string $(D man) as a Number and returns it.

--------------------
Number:
    Digit
    Digit Number
--------------------
 */
private Demangle!(string) parseNumber(string man) pure
{
    auto num = span!(isDigit)(man);
    expect(num.length != 0, "decimal digit expected", man);

    return typeof(return)(man[0 .. num.length], num);
}

unittest
{
    enum dem1 = parseNumber("123x");
    static assert(dem1.mangle == "123");
    static assert(dem1.content == "123");

    enum dem2 = parseNumber("9999999999999999999999999");
    static assert(dem2.mangle == "9999999999999999999999999");
    static assert(dem2.content == "9999999999999999999999999");

    static assert(throws!parseNumber("-42")); // sign
    static assert(throws!parseNumber("")); // empty
}

// Returns true if the letter ch matches Digit.
package bool isDigit(char ch) pure nothrow
{
    return '0' <= ch && ch <= '9';
}

// Returns true if the string man is expected to be a Number.
private bool isNumber(string man) pure nothrow
{
    return man.length && isDigit(man[0]);
}


/***************************************
Parses the string $(D man) as a HexNumber and returns it.

--------------------
HexNumber:
    HexDigit
    HexDigit HexNumber
--------------------
 */
private Demangle!(string) parseHexNumber(string man) pure
{
    auto num = span!(isHexDigit)(man);
    expect(num.length != 0, "hexadecimal digit expected", man);

    return typeof(return)(man[0 .. num.length], num);
}

unittest
{
    enum dem1 = parseHexNumber("1AFx");
    static assert(dem1.mangle == "1AF");
    static assert(dem1.content == "1AF");

    enum dem2 = parseHexNumber("FFFFFFFFFFFFFFFFFFFFFFFFF");
    static assert(dem2.mangle == "FFFFFFFFFFFFFFFFFFFFFFFFF");
    static assert(dem2.content == "FFFFFFFFFFFFFFFFFFFFFFFFF");

    static assert(throws!parseHexNumber("abc")); // lowercase
    static assert(throws!parseHexNumber("")); // empty
}

// Returns true if the letter ch matches HexFloat.
package bool isHexDigit(char ch) pure nothrow
{
    return isDigit(ch) || ('A' <= ch && ch <= 'F');
}

// Returns true if the string man is expected to be a HexNumber.
private bool isHexNumber(string man) pure nothrow
{
    return man.length && isHexDigit(man[0]);
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Type
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Parses the string $(D man) as a mangled type name and returns a
$(D Type) object representing the type.
 */
private Demangle!(Type) parseType(string man) pure
out
{
    assert(isType(man));
}
body
{
    switch (man.length ? man[0] : char.init)
    {
        case 'O', // Shared
             'x', // Const
             'y': // Invariant
            return parseTypeStoc(man);

        case 'A': // TypeArray
            return parseTypeArray(man);

        case 'G': // TypeSArray
            return parseTypeStaticArray(man);

        case 'H': // TypeAarray
            return parseTypeAssocArray(man);

        case 'P': // TypePointer
            return parseTypePointer(man);

        case 'F', 'U', 'W', 'V', 'R': // TypeFunction
            return parseTypeFunction(man);

        case 'I', // TypeIdent
             'C', // TypeClass
             'S', // TypeStruct
             'E', // TypeEnum
             'T': // TypeTypedef
            return parseTypeIdent(man);

        case 'D': // TypeDelegate
            return parseTypeDelegate(man);

        case 'n', // TypeNone
             'v', // TypeVoid
             'g', // TypeByte
             'h', // TypeUbyte
             's', // TypeShort
             't', // TypeUshort
             'i', // TypeInt
             'k', // TypeUint
             'l', // TypeLong
             'm', // TypeUlong
             'f', // TypeFloat
             'd', // TypeDouble
             'e', // TypeReal
             'o', // TypeIfloat
             'p', // TypeIdouble
             'j', // TypeIreal
             'q', // TypeCfloat
             'r', // TypeCdouble
             'c', // TypeCreal
             'b', // TypeBool
             'a', // TypeChar
             'u', // TypeWchar
             'w': // TypeDchar
            return parseTypeBasic(man);

        case 'B': // TypeTuple
            return parseTypeTuple(man);

        default:
            error("not a type", man);
            assert(0);
    }
}

unittest
{
    static assert(throws!parseType("0")); // not a type
    static assert(throws!parseType("")); // empty
}

// Returns true if the string man is expected to be a Type.
private bool isType(string man) pure nothrow
{
    if (!man.length)
        return false;

    static immutable bool[0x80] TYPE_CHARS =
    [
        'O': true, 'x': true, 'y': true,
        'A': true, 'G': true, 'H': true, 'P': true,
        'F': true, 'U': true, 'W': true, 'V': true, 'R': true,
        'I': true, 'C': true, 'S': true, 'E': true, 'T': true,
        'D': true,
        'n': true, 'v': true,
        'g': true, 's': true, 'i': true, 'l': true,
        'h': true, 't': true, 'k': true, 'm': true,
        'f': true, 'd': true, 'e': true,
        'o': true, 'p': true, 'j': true,
        'q': true, 'r': true, 'c': true,
        'b': true, 'a': true, 'u': true, 'w': true,
        'B': true
    ];
    const ch = man[0];
    return ch < TYPE_CHARS.length && TYPE_CHARS[ch];
}


/***************************************
Parses the string $(D man) as a mangled storage class and a type name
and returns a $(D Type) object representing the type and the storage
class.

--------------------
StorageClass:
    Shared
    Const
    Invariant

Shared:
    O Type

Const:
    x Type

Invariant:
    y Type
--------------------
 */
private Demangle!(Type) parseTypeStoc(string man) pure
{
    string rem = man;

    // the storage class
    alias StorageClass STC;
    STC stoc;

    switch (rem.length ? rem[0] : char.init)
    {
        case 'O': stoc = STC.   SHARED; break;
        case 'x': stoc = STC.    CONST; break;
        case 'y': stoc = STC.IMMUTABLE; break;

        default:
            error("not a storage class", man);
            assert(0);
    }
    rem = rem[1 .. $];

    // Extract the modified type. Note: Another storage class may be
    // applied to the modified type (in the case of shared const), so
    // we must add (or-assign) the storage class, not assign it.
    Type modty;

    auto next = parseType(rem);
    rem   = rem[next.mangle.length .. $];
    modty = next.content;

    // Add the storage class.
    modty.storage |= stoc;

    return typeof(return)(man[0 .. $ - rem.length], modty);
}

unittest
{
    enum dem1 = parseType("OiZ");
    static assert(dem1.mangle == "Oi");
    static assert(toString(dem1.content) == "shared(int)");

    enum dem2 = parseType("xiZ");
    static assert(dem2.mangle == "xi");
    static assert(toString(dem2.content) == "const(int)");

    enum dem3 = parseType("yiZ");
    static assert(dem3.mangle == "yi");
    static assert(toString(dem3.content) == "immutable(int)");

    enum dem4 = parseType("OxiZ");
    static assert(dem4.mangle == "Oxi");
    static assert(toString(dem4.content) == "shared(const(int))");

    static assert(throws!parseTypeStoc("i")); // no storage class
    static assert(throws!parseTypeStoc("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled dynamic array type name and
returns a $(D Type) object representing the type.

--------------------
TypeArray:
    A Type
--------------------
 */
private Demangle!(Type) parseTypeArray(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "A"), "not an array type", rem);
    rem = rem[1 .. $];

    // the element type
    auto etype = parseType(rem);
    rem = rem[etype.mangle.length .. $];

    // Compose a Type object.
    Type ty;
    ty.kind = Type.Kind.ARRAY;
    ty.next = [ etype.content ];

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    enum dem1 = parseType("AiZ");
    static assert(dem1.mangle == "Ai");
    static assert(toString(dem1.content) == "int[]");

    static assert(throws!parseTypeArray("AZ")); // no type
    static assert(throws!parseTypeArray("i")); // not an array
    static assert(throws!parseTypeArray("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled static array type name and
returns a $(D Type) object representing the type.

--------------------
TypeSarray:
    G Number Type
--------------------
 */
private Demangle!(Type) parseTypeStaticArray(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "G"), "not a static array type", rem);
    rem = rem[1 .. $];

    // the dimension of the static array
    auto dim = parseNumber(rem);
    rem = rem[dim.mangle.length .. $];

    // the element type
    auto etype = parseType(rem);
    rem = rem[etype.mangle.length .. $];

    // Compose a Type object.
    Type ty;
    ty.kind   = Type.Kind.SARRAY;
    ty.next   = [ etype.content ];
    ty.length = toSize(dim.content);

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    enum dem1 = parseType("G42iZ");
    static assert(dem1.mangle == "G42i");
    static assert(toString(dem1.content) == "int[42]");

    enum dem2 = parseType("G0i");
    static assert(dem2.mangle == "G0i");
    static assert(toString(dem2.content) == "int[0]");

    enum dem3 = parseType("G4294967295i");
    static assert(dem3.mangle == "G4294967295i");
    static assert(toString(dem3.content) == "int[4294967295]");

    static assert(throws!parseTypeStaticArray("G42")); // no type
    static assert(throws!parseTypeStaticArray("Gi")); // no dim
    static assert(throws!parseTypeStaticArray("G")); // neither
    static assert(throws!parseTypeStaticArray("i")); // invalid
    static assert(throws!parseTypeStaticArray("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled associative array type name and
returns a $(D Type) object representing the type.

--------------------
TypeAarray:
    H Type Type
--------------------
 */
private Demangle!(Type) parseTypeAssocArray(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "H"), "not an associative array type", rem);
    rem = rem[1 .. $];

    // Extract the referenced types. The value type precedes.
    auto vtype = parseType(rem);
    rem = rem[vtype.mangle.length .. $];

    auto ktype = parseType(rem);
    rem = rem[ktype.mangle.length .. $];

    // Compose a Type object.
    Type ty;
    ty.kind = Type.Kind.AARRAY;
    ty.next = [ ktype.content, vtype.content ]; // key precedes

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    enum dem1 = parseType("HieZ");
    static assert(dem1.mangle == "Hie");
    static assert(toString(dem1.content) == "int[real]");

    static assert(throws!parseTypeAssocArray("HiZ")); // no key
    static assert(throws!parseTypeAssocArray("HZ")); // no v/k
    static assert(throws!parseTypeAssocArray("i")); // invalid
    static assert(throws!parseTypeAssocArray("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled pointer type name and returns a
$(D Type) object representing the type.

--------------------
TypePointer:
    P Type
--------------------
 */
private Demangle!(Type) parseTypePointer(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "P"), "not a pointer type", rem);
    rem = rem[1 .. $];

    // the referenced type
    auto etype = parseType(rem);
    rem = rem[etype.mangle.length .. $];

    // Compose a Type object.
    Type ty;
    ty.kind = Type.Kind.POINTER;
    ty.next = [ etype.content ];

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    enum dem1 = parseType("PiZ");
    static assert(dem1.mangle == "Pi");
    static assert(toString(dem1.content) == "int*");

    static assert(throws!parseTypePointer("PZ")); // no type
    static assert(throws!parseTypePointer("i")); // not a pointer
    static assert(throws!parseTypePointer("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled function type name and returns
a $(D Type) object representing the type.

--------------------
TypeFunction:
    CallConvention FuncAttrs Arguments ArgClose Type

CallConvention:
    F       // D
    U       // C
    W       // Windows
    V       // Pascal
    R       // C++

FuncAttrs:
    empty
    FuncAttr
    FuncAttr FuncAttrs

FuncAttr:
    Na      // pure
    Nb      // nothrow
    Nc      // ref

ArgClose
    X       // variadic T t...) style
    Y       // variadic T t,...) style
    Z       // not variadic
--------------------
 */
private Demangle!(Type) parseTypeFunction(string man) pure
{
    string rem = man;

    /* A mangled function type name starts with a letter that indicates
     * the calling convention. The letter must not be omitted.
     */
    Linkage conv;

    switch (rem.length ? rem[0] : char.init)
    {
        case 'F': conv = Linkage.      D; break;
        case 'U': conv = Linkage.      C; break;
        case 'W': conv = Linkage.WINDOWS; break;
        case 'V': conv = Linkage. PASCAL; break;
        case 'R': conv = Linkage.    CPP; break;

        default:
            error("not a function type", rem);
            assert(0);
    }
    rem = rem[1 .. $];

    /* Extract zero or more function attributes. A function attribute
     * is mangled to an ASCII letter preceded by another letter 'N'.
     */
    FunctionAttribute atts;

    while (rem.length >= 2 && rem[0] == 'N')
    {
        alias FunctionAttribute Attr;

        switch (rem[1])
        {
            case 'a': atts |= Attr.   PURE; break;
            case 'b': atts |= Attr.NOTHROW; break;
            case 'c': atts |= Attr.    REF; break;

            default:
                error("invalid function attribute", rem);
                assert(0);
        }
        rem = rem[2 .. $];
    }

    /* Extract the parameter type list. The number of parameters is not
     * given. Just extract types until encountering an ArgClose.
     */
    auto args = parseArguments(rem);
    rem = rem[args.mangle.length .. $];

    /* There must be a letter indicating the function variadicity:
     *   'X' => typesafe
     *   'Y' => argptr
     *   'Z' => not variadic
     */
    Variadic var;

    switch (rem.length ? rem[0] : char.init)
    {
        case 'X': var = Variadic.TYPESAFE; break;
        case 'Y': var = Variadic.VARIADIC; break;
        case 'Z':   /* not variadic */     break;

        default:
            error("X, Y or Z expected", rem);
            assert(0);
    }
    rem = rem[1 .. $];

    // the return type
    auto rtype = parseType(rem);
    rem = rem[rtype.mangle.length .. $];

    // Compose a Type object.
    Type ty;
    ty.kind       = Type.Kind.FUNCTION;
    ty.next       = rtype.content ~ args.content;
    ty.linkage    = conv;
    ty.attributes = atts;
    ty.variadic   = var;

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    enum dem1 = parseType("FisZd0");
    static assert(dem1.mangle == "FisZd");
    static assert(toString(dem1.content) == "double(int, short)");

    enum dem2 = parseType("UNbNckMAxiXe0");
    static assert(dem2.mangle == "UNbNckMAxiXe");
    static assert(toString(dem2.content) ==
            "extern(C) nothrow ref real(uint, scope const(int)[]...)");

    enum dem3 = parseType("FYv0");
    static assert(dem3.mangle == "FYv");
    static assert(toString(dem3.content) == "void(...)");

    alias throws!parseTypeFunction invalid;
    static assert(invalid("F0")); // no return type
    static assert(invalid("FZ0")); // no return type
    static assert(invalid("FNzZv0")); // invalid attr
    static assert(invalid("Z")); // not a function
    static assert(invalid("")); // empty
}


/***************************************
Parses the string $(D man) as up to $(D max) mangled function parameter
type names and returns an array of $(D Type) objects representing the
parameter types.

--------------------
Arguments:
    Argument
    Argument Arguments

Argument:
    Argument2
    M Argument2     // scope

Argument2:
    Type
    J Type      // out
    K Type      // ref
    L Type      // lazy
--------------------
 */
private Demangle!(Type[]) parseArguments(
        in string man, size_t max = size_t.max) pure
{
    string rem = man;
    Type[] args;

    foreach (i; 0 .. max)
    {
        alias StorageClass STC;

        if (!rem.length || isArgClose(rem))
            break;

        /* Extract a parameter storage class. Beware of the possible
         * lazy scope storage class.
         */
        STC stc;

        while (rem.length)
        {
            STC c;

            switch (rem[0])
            {
                case 'M': c = STC.SCOPE; break;
                case 'J': c = STC.  OUT; break;
                case 'K': c = STC.  REF; break;
                case 'L': c = STC. LAZY; break;
                default: break;
            }
            if (c == STC.init)
                break; // no storage class

            // accumulate
            stc |= c;
            rem  = rem[1 .. $];
        }

        /* Extract a parameter type and add the parameter storage
         * class. Note: The parameter storage is independent of a
         * possible type-constructing storage class, so we must add
         * (or-assign) the parameter storage class, not assign it.
         */
        Type arg;

        auto type = parseType(rem);
        rem = rem[type.mangle.length .. $];
        arg = type.content;

        // Add the parameter storage class.
        arg.storage |= stc;

        // accumulate
        args ~= arg;
    }

    // Done.
    return typeof(return)(man[0 .. $ - rem.length], args);
}

unittest
{
    enum dem1 = parseArguments("iZ");
    static assert(dem1.mangle == "i");
    static assert(dem1.content.length == 1);
    static assert(toString(dem1.content[0]) == "int");

    enum dem2 = parseArguments("ike");
    static assert(dem2.mangle == "ike");
    static assert(dem2.content.length == 3);
    static assert(toString(dem2.content[0]) ==  "int");
    static assert(toString(dem2.content[1]) == "uint");
    static assert(toString(dem2.content[2]) == "real");

    enum dem3 = parseArguments("MLAxiZ");
    static assert(dem3.mangle == "MLAxi");
    static assert(dem3.content.length == 1);
    static assert(toString(dem3.content[0]) ==
            "lazy scope const(int)[]");

    enum dem4 = parseArguments("ike", 1);
    static assert(dem4.mangle == "i");
    static assert(dem4.content.length == 1);
    static assert(toString(dem4.content[0]) ==  "int");

    enum dem5 = parseArguments("");
    static assert(dem5.content == null);
}

// Returns true if the string man matches ArgClose.
private bool isArgClose(string man) pure nothrow
{
    switch (man.length ? man[0] : char.init)
    {
        case 'X', 'Y', 'Z': return  true;
        default           : return false;
    }
}


/***************************************
Parses the string $(D man) as a mangled user-defined type name and
returns a $(D Type) obejct representing the type.

A mangled user-defined type name only contains the user-defined name.

--------------------
TypeUser:
    TypeIdent
    TypeClass
    TypeStruct
    TypeEnum
    TypeTypedef

TypeIdent:
    I QualifiedName

TypeClass:
    C QualifiedName

TypeStruct:
    S QualifiedName

TypeEnum:
    E QualifiedName

TypeTypedef:
    T QualifiedName
--------------------
 */
private Demangle!(Type) parseTypeIdent(string man) pure
{
    alias Type.Kind T;
    string rem = man;

    // which type?
    T kind;

    switch (rem.length ? rem[0] : char.init)
    {
        case 'I': kind = T.  IDENT; break;
        case 'C': kind = T.  CLASS; break;
        case 'S': kind = T. STRUCT; break;
        case 'E': kind = T.   ENUM; break;
        case 'T': kind = T.TYPEDEF; break;

        default:
            error("I, C, S, E or T expected", rem);
            assert(0);
    }
    rem = rem[1 .. $];

    // the user-defined name
    auto name = parseQualifiedName(rem);
    rem = rem[name.mangle.length .. $];

    // Compose a Type object.
    Type ty;
    ty.kind   = kind;
    ty.symbol = [ name.content ];

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    alias Type.Kind T;

    enum dem1 = parseType("S3std5regex6EngineV");
    enum t1   = dem1.content;
    static assert(dem1.mangle == "S3std5regex6Engine");
    static assert(t1.kind == T.STRUCT);
    static assert(toString(t1.symbol[0]) == "std.regex.Engine");

    enum dem2 = parseType("C3Foo");
    enum t2   = dem2.content;
    static assert(dem2.mangle == "C3Foo");
    static assert(t2.kind == T.CLASS);
    static assert(toString(t2.symbol[0]) == "Foo");

    static assert(throws!parseTypeIdent("IZ")); // no qname
    static assert(throws!parseTypeIdent("")); //empty
}


/***************************************
Parses the string $(D man) as a mangled delegate type name and returns
a $(D Type) object representing the type.

--------------------
TypeDelegate:
    D TypeFunction
--------------------
 */
private Demangle!(Type) parseTypeDelegate(string man) pure
{
    string rem = man;

    // TypeDelegate is actually a TypeFunction prefixed by "D"
    expect(startsWith(rem, "D"), "not a delegate type", rem);
    rem = rem[1 .. $];

    auto fun = parseTypeFunction(rem);
    rem = rem[fun.mangle.length .. $];

    // Mark the returned function type as a delegate.
    Type ty = fun.content;
    ty.kind = Type.Kind.DELEGATE;

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    enum dem1 = parseType("DFNcAiXiZ");
    static assert(dem1.mangle == "DFNcAiXi");
    static assert(toString(dem1.content) == "ref int delegate(int[]...)");

    static assert(throws!parseTypeDelegate("FZv")); // not a dg
    static assert(throws!parseTypeDelegate("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled basic type name and returns a
$(D Type) object representing the type.
 */
private Demangle!(Type) parseTypeBasic(string man) pure
{
    alias Type.Kind T;

    expect(man.length != 0, "out of input", man);

    /* Use static array to map a mangled basic type name c to the
     * corresponding type kind. Invalid mangled name will be mapped to
     * T.init, which equals to T.NONE. However, T.NONE is a valid type
     * kind whose mangled name is 'n', so a special treatment will be
     * needed for c == 'n' when we are checking the input for an error.
     */
    static immutable T[0x80] MAP =
    [
        'n': T.  NONE, 'v': T.   VOID,
        'g': T.  BYTE, 's': T.  SHORT, 'i': T.  INT, 'l': T. LONG,
        'h': T. UBYTE, 't': T. USHORT, 'k': T. UINT, 'm': T.ULONG,
        'f': T. FLOAT, 'd': T. DOUBLE, 'e': T. REAL,
        'o': T.IFLOAT, 'p': T.IDOUBLE, 'j': T.IREAL,
        'q': T.CFLOAT, 'r': T.CDOUBLE, 'c': T.CREAL,
        'b': T.  BOOL, 'a': T.   CHAR, 'u': T.WCHAR, 'w': T.DCHAR,
    ];
    const c = man[0];

    if (c >= MAP.length || (c != 'n' && MAP[c] == T.init))
        error("not a basic type", man);

    return typeof(return)(man[0 .. 1], Type(MAP[c]));
}

unittest
{
    enum dem1 = parseType("ik");
    static assert(dem1.mangle == "i");
    static assert(toString(dem1.content) == "int");

    static assert(throws!parseTypeBasic("xi")); // storage class
    static assert(throws!parseTypeBasic("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled type tuple and returns a
$(D Type) object representing the type.

--------------------
TypeTuple:
    B Number Arguments
--------------------
 */
private Demangle!(Type) parseTypeTuple(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "B"), "not a type tuple", rem);
    rem = rem[1 .. $];

    // the number of items in the type tuple
    auto nargs = parseNumber(rem);
    rem = rem[nargs.mangle.length .. $];

    const dim = toSize(nargs.content);

    // Extract the items in the type tuple. Note: parseArguments
    // stops at (possible) ArgClose even if the number of extracted
    // items is less than dim.
    auto args = parseArguments(rem, dim);
    rem = rem[args.mangle.length .. $];

    expect(args.content.length == dim, "type tuple out of items", rem);

    // Compose a Type object.
    Type ty;
    ty.kind = Type.Kind.TUPLE;
    ty.next = args.content;

    return typeof(return)(man[0 .. $ - rem.length], ty);
}

unittest
{
    enum dem1 = parseType("B0Z");
    static assert(dem1.mangle == "B0");
    static assert(toString(dem1.content) == "()");

    enum dem2 = parseType("B2ixk");
    static assert(dem2.mangle == "B2ixk");
    static assert(toString(dem2.content) == "(int, const(uint))");

    static assert(throws!parseTypeTuple(
                "B9999999999999999999999999z")); // overflow
    static assert(throws!parseTypeTuple("B2iZ")); // out of item
    static assert(throws!parseTypeTuple("Bz")); // no number
    static assert(throws!parseTypeTuple("B100")); // no type
}


/***************************************
Parses the string $(D man) as a SymbolType. SymbolType is used in
Symbol and MangledName for representing the type of a symbol.

--------------------
SymbolType:
    Type
    M Type
--------------------
 */
private Demangle!(Type) parseSymbolType(string man) pure
{
    string rem = man;

    // A possible preceding M indicates that the symbol is a function
    // that needs a context pointer.
    bool needthis;

    if (startsWith(rem, "M"))
    {
        needthis = true;
        rem = rem[1 .. $];
    }

    // the symbol type
    auto demty = parseType(rem);
    rem = rem[demty.mangle.length .. $];

    auto type = demty.content;
    type.needThis = needthis;

    return typeof(return)(man[0 .. $ - rem.length], type);
}

unittest
{
    enum st1 = parseSymbolType("MFZv");
    static assert(st1.content.needThis);
}

// Returns true if the string man is expected to be a SymbolType.
private bool isSymbolType(string man) pure nothrow
{
    return startsWith(man, "M") || isType(man);
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Symbol name
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Returns $(D true) if the string $(D id) is a valid identifier.

--------------------
Identifier:
    IdentiferStart
    IdentiferStart IdentifierChars

IdentifierChars:
    IdentiferChar
    IdentiferChar IdentifierChars

IdentifierStart:
    _
    Letter
    UniversalAlpha

IdentifierChar:
    IdentiferStart
    0
    NonZeroDigit
--------------------
 */
private bool isIdentifier(string id) pure nothrow
{
    static bool isIdentifierStart(char ch) pure nothrow
    {
        return ('a' <= ch && ch <= 'z') ||
               ('A' <= ch && ch <= 'Z') ||
               (ch == '_') || (ch >= 0x80);
    }

    static bool isIdentifierChar(char ch) pure nothrow
    {
        return isIdentifierStart(ch) ||
               ('0' <= ch && ch <= '9');
    }

    if (!id.length || !isIdentifierStart(id[0]))
        return false;

    foreach (c; id[1 .. $])
    {
        if (!isIdentifierChar(c))
            return false;
    }
    return true;
}

unittest
{
    static assert( isIdentifier("__unittest1"));
    static assert( isIdentifier("errno"));
    static assert( isIdentifier("\u03B1"));
    static assert(!isIdentifier("4test"));
    static assert(!isIdentifier(" "));
}


/***************************************
Parses the string $(D man) as a mangled qualified name and returns a
$(D Symbol) object representing the qualified name.

--------------------
QualifiedName:
    TypedSymbol
    TypedSymbol QualifiedName

TypedSymbol:
    Symbol
    Symbol SymbolType
--------------------
 */
private Demangle!(Symbol) parseQualifiedName(string man) pure
{
    string rem = man;

    Symbol qname;
    uint   depth;
    do
    {
        Symbol segment;

        auto sym = parseSymbolName(rem);
        rem     = rem[sym.mangle.length .. $];
        segment = sym.content;

        // Functions and variables have their own types. Beware of
        // nested functions; in such case intermediate segments may
        // have types (not documented in the ABI).
        if (isSymbolType(rem))
        {
            try
            {
                auto type = parseSymbolType(rem);
                rem          = rem[type.mangle.length .. $];
                segment.type = [ type.content ];
            }
            catch
            {
                // May have wrongly parsed a template value parameter
                // "V..." as a function type. It can happen.
            }
        }

        // Connect to the parent segment.
        if (++depth > 1)
            segment.parent = [ qname ];
        qname = segment;
    }
    while (isSymbolName(rem))

    return typeof(return)(man[0 .. $ - rem.length], qname);
}

unittest
{
    enum dem1 = parseQualifiedName("3std4math");
    static assert(dem1.mangle == "3std4math");
    static assert(toString(dem1.content) == "std.math");

    enum dem2 = parseQualifiedName("3std6traits__T6UnqualTxiZZ");
    static assert(dem2.mangle == "3std6traits__T6UnqualTxiZ");
    static assert(toString(dem2.content) ==
            "std.traits.Unqual!(const(int))");

    static assert(throws!parseQualifiedName("zzz")); // invalid
    static assert(throws!parseQualifiedName("")); // empty
}

// Returns true if the string man is expected to be a QualifiedName.
private bool isQualifiedName(string man) pure nothrow
{
    return isSymbolName(man);
}


/***************************************
Parses the string $(D man) as a mangled symbol name and returns a
$(D Symbol) object representing the symbol.

--------------------
Symbol:
    LName
    TemplateInstanceName
    main                    // special name
--------------------

BUGS:
Cannot deal with special symbol names such as "main".
 */
private Demangle!(Symbol) parseSymbolName(string man) pure
{
    if (isLName(man))
    {
        string rem = man;
        Symbol sym;

        auto lname = parseLName(rem);
        rem = rem[lname.mangle.length .. $];
        sym = lname.content;

        // [workaround] Bugzilla #3034
        if (isTemplateInstanceName(sym.name))
        {
            try
            {
                sym = finish!parseTemplateInstanceName(sym.name);
            }
            catch {}
        }

        return typeof(return)(man[0 .. $ - rem.length], sym);
    }
    else if (isTemplateInstanceName(man))
    {
        return parseTemplateInstanceName(man);
    }
    else if (isSpecialSymbol(man))
    {
        return parseSpecialSymbol(man);
    }

    error("not a symbol", man);
    assert(0);
}

unittest
{
    enum dem1 = parseSymbolName("6nonstd0");
    static assert(dem1.mangle == "6nonstd");
    static assert(toString(dem1.content) == "nonstd");

    enum dem2 = parseSymbolName("__T4TestZ0");
    static assert(dem2.mangle == "__T4TestZ");
    static assert(toString(dem2.content) == "Test!()");

    static assert(throws!parseSymbolName("0")); // not an ident
    static assert(throws!parseSymbolName("_D4testi")); // not a sym
    static assert(throws!parseSymbolName("")); // empty
}

// Returns true if the string man is expected to be a Symbol.
private bool isSymbolName(string man) pure nothrow
{
    return isLName(man) ||
           isTemplateInstanceName(man) ||
           isSpecialSymbol(man);
}


/***************************************
Parses the string $(D man) as a mangled identifier name and returns a
$(D Symbol) object representing the identifier.

--------------------
LName:
    Number Name
--------------------
 */
private Demangle!(Symbol) parseLName(string man) pure
{
    string rem = man;

    // Extract the length of the identifier. Note that the length may
    // be too big v.s. the input string.
    auto num = parseNumber(rem);
    rem = rem[num.mangle.length .. $];

    expect(rem.length >= toSize(num.content), "out of input", rem);

    // Extract the identifier by simply slicing the input. Note that
    // the obtained string may not be a valid identifier.
    const id = rem[0 .. toSize(num.content)];
    expect(isIdentifier(id), "invalid identifier: " ~ id, rem);
    rem = rem[id.length .. $];

    // Compose a Symbol object.
    Symbol sym;
    sym.kind = Symbol.Kind.IDENTIFIER;
    sym.name = id;

    return typeof(return)(man[0 .. $ - rem.length], sym);
}

unittest
{
    enum dem1 = parseLName("3std0");
    static assert(dem1.mangle == "3std");
    static assert(toString(dem1.content) == "std");

    alias throws!parseLName invalid;
    static assert(invalid("42a")); // out of input
    static assert(invalid("8std.math")); // invalid identifier
    static assert(invalid("__T4TestZ")); // not an LName
    static assert(invalid("")); // empty

    // overflow
    enum max = toString(cast(uintmax_t) size_t.max);
    static assert(invalid(max ~ "z"));
}

// Returns true if the string man is expected to be an LName.
private bool isLName(string man) pure nothrow
{
    return isNumber(man);
}


/***************************************
Parses the string $(D man) as a mangled template instance name and
returns a $(D Symbol) object representing the template instance.

--------------------
TemplateInstanceName:
     __T LName TemplateArgs Z

TemplateArgs:
    TemplateArg
    TemplateArg TemplateArgs
--------------------
 */
private Demangle!(Symbol) parseTemplateInstanceName(string man) pure
{
    string rem = man;

    // Expect "__T"
    expect(startsWith(rem, "__T"), "not a template instance name", rem);
    rem = rem[3 .. $];

    // the name of the instantiated template itself
    auto name = parseLName(rem);
    rem = rem[name.mangle.length .. $];

    // the template instantiation arguments
    TemplateArgument[] args;

    while (isTemplateArg(rem))
    {
        auto ta = parseTemplateArg(rem);
        rem   = rem[ta.mangle.length .. $];
        args ~= ta.content;
    }

    // expect "Z"
    expect(startsWith(rem, "Z"), "template instance not closed", rem);
    rem = rem[1 .. $];

    // Compose a Symbol object for the template instance.
    Symbol sym;
    sym.kind = Symbol.Kind.TEMPLATE;
    sym.name = name.content.name;
    sym.args = args;

    return typeof(return)(man[0 .. $ - rem.length], sym);
}

unittest
{
    enum dem1 = parseTemplateInstanceName("__T4TestZ0");
    static assert(dem1.mangle == "__T4TestZ");
    static assert(toString(dem1.content) == "Test!()");

    enum dem2 = parseTemplateInstanceName("__T4TestTiVii42Z");
    static assert(dem2.mangle == "__T4TestTiVii42Z");
    static assert(toString(dem2.content) == "Test!(int, 42)");

    alias throws!parseTemplateInstanceName invalid;
    static assert(invalid("__T4Test")); // no Z
    static assert(invalid("__TTiZ")); // no LName
    static assert(invalid("4Test")); // not TIN
    static assert(invalid("")); // empty
}

// Returns true if the string man is expected to be a
// TemplateInstanceName.
private bool isTemplateInstanceName(string man) pure nothrow
{
    return startsWith(man, "__T");
}


/***************************************
Parses the string $(D man) as a mangled template argument and returns
a $(D TemplateArgument) object representing the template argument.

--------------------
TemplateArg:
    T Type
    V Type Value
    S TemplateSymbolArg

TemplateSymbolArg:
    M LName
    QualifiedName
--------------------
 */
private Demangle!(TemplateArgument) parseTemplateArg(string man) pure
{
    // hub
    switch (man.length ? man[0] : char.init)
    {
        case 'T': return parseTemplateTypeArg(man);
        case 'V': return parseTemplateValueArg(man);
        case 'S': return parseTemplateSymbolArg(man);

        default:
            error("not a template argument", man);
            assert(0);
    }
}

unittest
{
    alias throws!parseTemplateTypeArg invalid;
    static assert(invalid("Z")); // not a targ
    static assert(invalid("")); // empty
}

// Returns true if the string man is expected to be a TemplateArg.
private bool isTemplateArg(string man) pure nothrow
{
    return man.length &&
        (man[0] == 'T' || man[0] == 'V' || man[0] == 'S');
}


/***************************************
Parses the string $(D man) as a mangled template type argument and
returns a $(D TemplateArgument) object representing the type.

--------------------
TemplateArg:
    T Type
--------------------
 */
private Demangle!(TemplateArgument)
    parseTemplateTypeArg(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "T"), "not a template type argument", rem);
    rem = rem[1 .. $];

    // Simply extract a type.
    auto type = parseType(rem);
    rem = rem[type.mangle.length .. $];

    // Compose a TemplateArgument object.
    TemplateArgument targ;
    targ.kind = TemplateArgument.Kind.TYPE;
    targ.type = type.content;

    return typeof(return)(man[0 .. $ - rem.length], targ);
}

unittest
{
    enum dem1 = parseTemplateTypeArg("TiZ");
    static assert(dem1.mangle == "Ti");
    static assert(toString(dem1.content) == "int");

    alias throws!parseTemplateTypeArg invalid;
    static assert(invalid("TZ")); // no type
    static assert(invalid("Vii42")); // not type
    static assert(invalid("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled template value argument and
returns a $(D TemplateArgument) object representing the value.

--------------------
TemplateArg:
    V Type Value
--------------------
 */
private Demangle!(TemplateArgument)
    parseTemplateValueArg(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "V"), "not a template value argument", rem);
    rem = rem[1 .. $];

    // Extract the type and value of the argument. The type gives the
    // value an explicit type (values don't have explicit type info).
    auto type = parseType(rem);
    rem = rem[type.mangle.length .. $];

    auto val = parseValue(rem);
    rem = rem[val.mangle.length .. $];

    // Compose a TemplateArgument object.
    TemplateArgument targ;
    targ.kind  = TemplateArgument.Kind.VALUE;
    targ.type  = type.content;
    targ.value = val.content;

    return typeof(return)(man[0 .. $ - rem.length], targ);
}

unittest
{
    enum dem1 = parseTemplateValueArg("Vki42Z");
    static assert(dem1.mangle == "Vki42");
    static assert(toString(dem1.content) == "42U");

    alias throws!parseTemplateValueArg invalid;
    static assert(invalid("V42")); // no type
    static assert(invalid("Vxi")); // no value
    static assert(invalid("S3std")); // not value
    static assert(invalid("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled template symbol argument and
returns a $(D TemplateArgument) object representing the symbol.

BUGS:
  $(BUGZILLA 3043) must be fixed.

--------------------
TemplateArg:
    S TemplateSymbolArg

TemplateSymbolArg:
    QualifiedName
    M LName
--------------------
 */
private Demangle!(TemplateArgument)
    parseTemplateSymbolArg(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "S"), "not a template symbol argument", rem);
    rem = rem[1 .. $];

    /* A symbol argument is encoded to a QualifiedName, or an LName
     * preceded by a letter 'M' (Bugzilla 3043).
     */
    Symbol sym;

    if (startsWith(rem, "M"))
    {
        rem = rem[1 .. $];

        // Extract the mangled name of the symbol.
        auto rawname = parseLName(rem);
        rem = rem[rawname.mangle.length .. $];

        /* Try to demangle the raw mangled name. If it is not a valid
         * mangled name, then use the raw name (not an error).
         */
        sym = rawname.content;

        if (isMangledName(sym.name))
        {
            try
            {
                sym = finish!parseMangledName(sym.name);
            }
            catch {}
        }
        else if (isCppMangledName(sym.name))
        {
            try
            {
                sym = finish!parseCppMangledName(sym.name);
            }
            catch {}
        }
    }
    else
    {
        // a fully qualified name
        auto qname = parseQualifiedName(rem);
        rem = rem[qname.mangle.length .. $];
        sym = qname.content;
    }

    // Compose a TemplateArgument object.
    TemplateArgument targ;
    targ.kind   = TemplateArgument.Kind.SYMBOL;
    targ.symbol = sym;

    return typeof(return)(man[0 .. $ - rem.length], targ);
}

unittest
{
    enum dem1 = parseTemplateArg("S3std4mathZ");
    static assert(dem1.mangle == "S3std4math");
    static assert(toString(dem1.content) == "std.math");

    enum dem2 = parseTemplateArg("SM15_D3std4math2PIe");
    static assert(dem2.mangle == "SM15_D3std4math2PIe");
    static assert(toString(dem2.content) == "real std.math.PI");

    enum dem3 = parseTemplateArg("SM13_ZN4IFoo3fooE");
    static assert(dem3.mangle == "SM13_ZN4IFoo3fooE");
    static assert(toString(dem3.content) == "IFoo.foo");

    enum dem4 = parseTemplateArg("SM6__Dabc");
    static assert(dem4.mangle == "SM6__Dabc");
    static assert(toString(dem4.content) == "__Dabc");

    static assert(throws!parseTemplateArg("SiZ")); // not a symbol
    static assert(throws!parseTemplateArg("")); // empty
}


/***************************************
Parses the string $(D man) as a special symbol name and returns a
$(D Symbol) object representing that symbol.

--------------------
SpecialSymbol:
    main
--------------------
 */
private Demangle!(Symbol) parseSpecialSymbol(string man) pure
{
    string rem = man;
    expect(isSpecialSymbol(rem), "not a special symbol", rem);

    const id = span!(isAsciiAlpha)(rem);
    rem = rem[id.length .. $];

    // Compose a Symbol object.
    Symbol sym;
    sym.kind = Symbol.Kind.IDENTIFIER;
    sym.name = id;

    return typeof(return)(man[0 .. $ - rem.length], sym);
}

unittest
{
    enum dem1 = parseSpecialSymbol("main");
    static assert(dem1.content.name == "main");

    alias throws!parseSpecialSymbol invalid;
    static assert(invalid("foo"));
    static assert(invalid("42"));
    static assert(invalid(""));
}

// Returns true if the string man is expected to be a SpecialSymbol.
private bool isSpecialSymbol(string man) pure nothrow
{
    switch (span!(isAsciiAlpha)(man))
    {
        case "main": return  true;
        default    : return false;
    }
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Literal value
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Parses the string $(D man) as a mangled constant value and returns a
$(D Literal) object representing the value.

--------------------
Value:
    n
    i Number                // positive integer
    i N Number              // negative integer
    e HexFloat
    c HexFloat c HexFloat
    A Number Value...
    a Number _ HexNumber
    w Number _ HexNumber
    d Number _ HexNumber
    S Number Value...       // struct literal
--------------------
 */
private Demangle!(Literal) parseValue(string man) pure
{
    enum NULL = Literal(Literal.Kind.NULL);

    switch (man.length ? man[0] : char.init)
    {
        case 'i': return parseNumericLiteral(man);
        case 'e': return parseFloatLiteral(man);
        case 'c': return parseComplexLiteral(man);
        case 'A': return parseArrayLiteral(man);
        case 'S': return parseStructLiteral(man);
        case 'a', 'w', 'd':
            return parseStringLiteral(man);
        case 'n':
            return typeof(return)(man[0 .. 1], NULL);

        // [workaround] Bugzilla #3029
        case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'N':
            return parseBareNumericLiteral(man);

        default:
            error("not a literal value", man);
            assert(0);
    }
}

unittest
{
    enum dem1 = parseValue("n");
    static assert(dem1.mangle == "n");
    static assert(toString(dem1.content) == "null");

    static assert(throws!parseValue("Z")); // not value
    static assert(throws!parseValue("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled integral constant value and
returns a $(D Literal) object representing the value.

--------------------
NumericLiteral:
    i Number
    i N Number
--------------------

BUG:
  Bugzilla #3029 must be fixed.
 */
private Demangle!(Literal) parseNumericLiteral(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "i"), "not a numeric literal", rem);
    rem = rem[1 .. $];

    auto bare = parseBareNumericLiteral(man[1 .. $]);
    rem = rem[bare.mangle.length .. $];

    return typeof(return)(man[0 .. $ - rem.length], bare.content);
}

// [internal] NumericLiteral without the prefix 'i'
private Demangle!(Literal) parseBareNumericLiteral(string man) pure
{
    string rem = man;

    // Extract the sign and digits. A sign is encoded to 'N'.
    bool neg;

    if (startsWith(rem, "N"))
    {
        rem = rem[1 .. $];
        neg = true;
    }

    auto num = parseNumber(rem);
    rem = rem[num.mangle.length .. $];

    // Huge unsigned numbers are really encoded to negative numbers, so
    // we can use toInt without fear of signed integer overflow.
    const val = toInt((neg ? "-" : "") ~ num.content);

    // Compose a Literal object.
    Literal lit;
    lit.kind    = Literal.Kind.INTEGER;
    lit.integer = cast(uintmax_t) val;

    return typeof(return)(man[0 .. $ - rem.length], lit);
}

unittest
{
    enum dem1 = parseValue("i42Z");
    static assert(dem1.mangle == "i42");
    static assert(dem1.content.integer == 42);

    enum dem2 = parseValue("iN42Z");
    static assert(dem2.mangle == "iN42");
    static assert(dem2.content.integer == cast(uintmax_t) -42);

    enum dem3 = parseValue("i0");
    static assert(dem3.mangle == "i0");
    static assert(dem3.content.integer == 0);

    alias throws!parseNumericLiteral invalid;
    static assert(invalid("42")); // needs prefix
    static assert(invalid("Z")); // not an integer
    static assert(invalid("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled floating point constant value
and returns a $(D Literal) object representing the value.

--------------------
FloatLiteral:
    e HexFloat
--------------------
 */
private Demangle!(Literal) parseFloatLiteral(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "e"), "not a floating point literal", rem);
    rem = rem[1 .. $];

    // Floating point value is encoded in hexadecimal format (e.g.
    // 1FFFP42, which represents 0x1.FFFp42).
    auto xf = parseHexFloat(rem);
    rem = rem[xf.mangle.length .. $];

    // Compose a Literal object.
    Literal val;
    val.kind = Literal.Kind.FLOAT;
    val.re   = xf.content;

    return typeof(return)(man[0 .. $ - rem.length], val);
}

unittest
{
    enum dem1 = parseValue("e1FFFP42Z");
    static assert(dem1.mangle == "e1FFFP42");
    static assert(dem1.content.re == 0x1.FFFp42L);

    enum dem2 = parseValue("eN1PN1076");
    static assert(dem2.mangle == "eN1PN1076");
    static assert(dem2.content.re == -0x1p-1076L);

    enum dem3 = parseValue("eNINFI");
    static assert(dem3.mangle == "eNINF");
    static assert(dem3.content.re == -real.infinity);

    alias throws!parseFloatLiteral invalid;
    static assert(invalid("e0")); // no HexFloat
    static assert(invalid("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled complex constant value and
returns a $(D Literal) object representing the value.

--------------------
ComplexLiteral:
    c HexFloat c HexFloat
--------------------
 */
private Demangle!(Literal) parseComplexLiteral(string man) pure
{
    string rem = man;

    // Extract re and im. Both of them are prefixed by a letter 'c'.
    real[] reim;

    foreach (i; 0 .. 2)
    {
        expect(startsWith(rem, "c"), "not a complex literal", rem);
        rem = rem[1 .. $];

        auto xf = parseHexFloat(rem);
        rem   = rem[xf.mangle.length .. $];
        reim ~= xf.content;
    }
    assert(reim.length == 2);

    // Compose a Literal object.
    Literal val;
    val.kind = Literal.Kind.COMPLEX;
    val.re   = reim[0];
    val.im   = reim[1];

    return typeof(return)(man[0 .. $ - rem.length], val);
}

unittest
{
    enum dem1 = parseValue("c12P3cN14PN5Z");
    static assert(dem1.mangle == "c12P3cN14PN5");
    static assert(toString(dem1.content) == "0x1.2p3 - 0x1.4p-5i");

    alias throws!parseComplexLiteral invalid;
    static assert(invalid("c0P0")); // no im
    static assert(invalid("cc0P0")); // no re
    static assert(invalid("")); // empty
}


/*
Parses the string $(D man) as a hex-mangled floating point value and
returns the $(D real) value.

This function is used by parseFloatLiteral and parseComplexLiteral.

--------------------
HexFloat:
    NAN
    INF
    NINF
    N HexDigits P Exponent  // negative
    HexDigits P Exponent    // positive

Exponent:
    N Number                // negative
    Number                  // positive
--------------------
 */
private Demangle!(real) parseHexFloat(string man) pure
{
    string rem = man;
    real val;

    // Deal with special values.
    if (startsWith(rem, "NAN"))
    {
        rem = rem[3 .. $];
        val = real.nan;
    }
    else if (startsWith(rem, "INF"))
    {
        rem = rem[3 .. $];
        val = +real.infinity;
    }
    else if (startsWith(rem, "NINF"))
    {
        rem = rem[4 .. $];
        val = -real.infinity;
    }
    // Otherwise it must be a usual finite real number.
    else
    {
        /* First build a hexadecimal string representing the value.
         * Then convert it to a real value.
         */
        string str;

        // sign
        if (startsWith(rem, "N"))
        {
            rem  = rem[1 .. $];
            str ~= "-";
        }
        str ~= "0x";

        /* Parse the mantissa part. It's a series of HexDigits. The
         * first HexDigit is the integer part (almost always 1), and
         * the rest is the fraction part.
         */
        auto mant = parseHexNumber(rem);
        rem = rem[mant.mangle.length .. $];

        // the integer part
        str ~= mant.content[0];

        // the fraction part (can be empty)
        if (mant.content.length > 1)
            str ~= "." ~ mant.content[1 .. $];

        /* Parse the exponent part. It's just a BareNumericLiteral
         * preceded by a letter 'P'.
         */
        expect(startsWith(rem, "P"), "exponent part expected", rem);
        rem = rem[1 .. $];

        auto exp = parseBareNumericLiteral(rem);
        rem = rem[exp.mangle.length .. $];

        str ~= "p" ~ toString(cast(intmax_t) exp.content.integer);

        // Now str should be a valid hex float string.
        val = toReal(str);
    }

    return typeof(return)(man[0 .. $ - rem.length], val);
}

unittest
{
    enum dem1 = parseHexFloat("1AFP10Z");
    static assert(dem1.mangle == "1AFP10");
    static assert(dem1.content == 0x1.AFp10L);

    enum dem2 = parseHexFloat("N1AFPN10Z");
    static assert(dem2.mangle == "N1AFPN10");
    static assert(dem2.content == -0x1.AFp-10L);

    enum dem3 = parseHexFloat("NANZ");
    static assert(dem3.mangle == "NAN");
    static assert(dem3.content !<>= 0);

    enum dem4 = parseHexFloat("INFZ");
    static assert(dem4.mangle == "INF");
    static assert(dem4.content == +real.infinity);

    enum dem5 = parseHexFloat("NINFZ");
    static assert(dem5.mangle == "NINF");
    static assert(dem5.content == -real.infinity);

    alias throws!parseHexFloat invalid;
    static assert(invalid("1AFP")); // no exp
    static assert(invalid("P42")); // no mantissa
    static assert(invalid("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled array literal and returns a
$(D Literal) object representing the array.

--------------------
ArrayLiteral:
    A LValues
--------------------
 */
private Demangle!(Literal) parseArrayLiteral(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "A"), "not an array", rem);
    rem = rem[1 .. $];

    auto items = parseLValues(rem);
    rem = rem[items.mangle.length .. $];

    // Compose a Literal object.
    Literal val;
    val.kind = Literal.Kind.ARRAY;
    val.next = items.content;

    return typeof(return)(man[0 .. $ - rem.length], val);
}

unittest
{
    enum dem1 = parseValue("A3i1i2i3Z");
    static assert(dem1.mangle == "A3i1i2i3");
    static assert(toString(dem1.content) == "[ 1, 2, 3 ]");

    enum dem2 = parseValue("A0");
    static assert(dem2.mangle == "A0");
    static assert(length(dem2.content.next) == 0);

    alias throws!parseArrayLiteral invalid;
    static assert(invalid("AZ")); // no dim
    static assert(invalid("A1Z")); // no elm
    static assert(invalid("")); // empty
}


/***************************************
Parses the string $(D man) as a mangled struct literal and returns a
$(D Literal) object representing the struct value.

--------------------
StructLiteral:
    S LValues
--------------------
 */
private Demangle!(Literal) parseStructLiteral(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "S"), "not a struct", rem);
    rem = rem[1 .. $];

    auto items = parseLValues(rem);
    rem = rem[items.mangle.length .. $];

    // Compose a Literal object.
    Literal val;
    val.kind = Literal.Kind.STRUCT;
    val.next = items.content;

    return typeof(return)(man[0 .. $ - rem.length], val);
}

unittest
{
    enum dem1 = parseValue("S3i1i2i3Z");
    static assert(dem1.mangle == "S3i1i2i3");
    static assert(toString(dem1.content) == "struct(1, 2, 3)");

    enum dem2 = parseValue("S0");
    static assert(dem2.mangle == "S0");
    static assert(length(dem2.content.next) == 0);

    alias throws!parseStructLiteral invalid;
    static assert(invalid("SZ")); // no dim
    static assert(invalid("S1Z")); // no elm
    static assert(invalid("")); // empty
}


/*
Parses the string $(D man) as zero or more consequent Literals and
returns an array of the literals.

--------------------
LValues:
    Number Value*
--------------------
 */
private Demangle!(Literal[]) parseLValues(string man) pure
{
    string rem = man;

    // the number of items expected
    auto dim = parseNumber(rem);
    rem = rem[dim.mangle.length .. $];

    // Extract exactly dim items.
    Literal[] items;

    foreach (i; 0 .. toSize(dim.content))
    {
        auto item = parseValue(rem);
        rem    = rem[item.mangle.length .. $];
        items ~= item.content;
    }
    return typeof(return)(man[0 .. $ - rem.length], items);
}


/***************************************
Parses the string $(D man) as a mangled string literal and returns a
$(D Literal) object representing the string.

--------------------
StringLiteral:
    a Number _ HexDigits    // UTF-8 string
    w Number _ HexDigits    // UTF-16 string (in UTF-8)
    d Number _ HexDigits    // UTF-32 string (in UTF-8)
--------------------
 */
private Demangle!(Literal) parseStringLiteral(string man) pure
{
    string rem = man;

    /* Detect the string suffix. Note that the UTF-8 suffix 'c' is
     * encoded to 'a'.
     */
    string suffix;

    switch (rem.length ? rem[0] : char.init)
    {
        case 'a': suffix = "c"; break; // UTF-8
        case 'w': suffix = "w"; break; // UTF-16
        case 'd': suffix = "d"; break; // UTF-32

        default:
            error("not a string literal", rem);
            assert(0);
    }
    rem = rem[1 .. $];

    // the length of the string in UTF-8 bytes
    auto num = parseNumber(rem);
    rem = rem[num.mangle.length .. $];
    const len = toSize(num.content);

    expect(startsWith(rem, "_"), "delimiter '_' expected", rem);
    rem = rem[1 .. $];

    /* The string is stored as a base-16 (lowercase hexadecimal)
     * formatted UTF-8 string.
     */
    static bool isLowerHexDigit(char ch) pure nothrow
    {
        return isDigit(ch) || ('a' <= ch && ch <= 'f');
    }

    // The length may be too big v.s. the input string.
    expect(len <= (rem.length + 1) / 2, "string out of input", rem);

    // Extract valid base-16 characters.
    string str = span!(isLowerHexDigit)(rem[0 .. 2 * len]);
    expect(str.length == 2 * len, "invalid base-16 string", rem);
    rem = rem[str.length .. $];

    str = decodeBase16String(str);

    // Compose a Literal object.
    Literal val;
    val.kind   = Literal.Kind.STRING;
    val.text   = str;
    val.suffix = suffix;

    return typeof(return)(man[0 .. $ - rem.length], val);
}

unittest
{
    enum dem1 = parseValue("a3_e381a7Z");
    static assert(dem1.mangle == "a3_e381a7");
    static assert(dem1.content.text   == x"e3 81 a7");
    static assert(dem1.content.suffix == "c");

    enum dem2 = parseValue("w0_");
    static assert(dem2.mangle == "w0_");
    static assert(dem2.content.text.length == 0);
    static assert(dem2.content.suffix == "w");

    alias throws!parseStringLiteral invalid;
    static assert(invalid("a_")); // no len
    static assert(invalid("a120")); // no _
    static assert(invalid("")); // empty
}


/*
Decodes the UTF-8 string encoded to lowercase hexadecimal digits byte
by byte.
 */
private string decodeBase16String(string x) pure nothrow
in
{
    assert(x.length % 2 == 0);
}
body
{
    static ubyte hexToNibble(char ch) pure nothrow
    {
        if ('0' <= ch && ch <= '9')
            return cast(ubyte) (ch - '0');
        if ('a' <= ch && ch <= 'f')
            return cast(ubyte) (ch - 'a' + 10);
        assert(0);
    }

    string s = "";

    for (size_t i = 0; i < x.length; )
    {
        const hi = hexToNibble(x[i++]);
        const lo = hexToNibble(x[i++]);

        s ~= cast(char) ((hi << 4) | lo);
    }
    return s;
}

unittest
{
    static assert(decodeBase16String("") == "");
    static assert(decodeBase16String("5a5b5c") == x"5a5b5c");
}


// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //
// Mangled Name
// : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : //

/***************************************
Parses the string $(D man) as a mangled D symbol name and returns a
$(D Symbol) object representing the symbol (varaible or function).

--------------------
MangledName:
    _D QualifiedName Type
    _D QualifiedName M Type
--------------------
 */
private Demangle!(Symbol) parseMangledName(string man) pure
{
    string rem = man;

    expect(startsWith(rem, "_D"), "not a D mangled name", rem);
    rem = rem[2 .. $];

    // Extract the fully qualified name. Type is handled by
    // parseQualifiedName.
    auto qname = parseQualifiedName(rem);
    rem = rem[qname.mangle.length .. $];

    return typeof(return)(man[0 .. $ - rem.length], qname.content);
}

unittest
{
    enum dem1 = parseMangledName("_D3std4math2PIe");
    static assert(dem1.mangle == "_D3std4math2PIe");
    static assert(toString(dem1.content) == "real std.math.PI");

    enum dem2 = parseMangledName("_D4core4stdc6strcpyUNbPaxPaZPa");
    static assert(dem2.mangle == "_D4core4stdc6strcpyUNbPaxPaZPa");
    static assert(toString(dem2.content) ==
            "extern(C) nothrow "
            "char* core.stdc.strcpy(char*, const(char*))");

    enum dem3 = parseMangledName("_Dmain");
    static assert(dem3.mangle == "_Dmain");
    static assert(dem3.content.name == "main");

    alias throws!parseMangledName invalid;
    static assert(invalid("_D")); // out of input
    static assert(invalid("")); // empty
}

// Returns true if the string man is expected to be a MangledName.
private bool isMangledName(string man) pure nothrow
{
    return startsWith(man, "_D");
}


//===================================================================//
// Limited support for C++ mangled names
//===================================================================//

/***************************************
Parses the string $(D man) as a C++ mangled symbol name and returns a
$(D Symbol) object representing the symbol.

BUGS:
Incomplete.

Reference:
http://www.codesourcery.com/public/cxx-abi/abi.html

--------------------
MangledName:
    _Z Encoding

Encoding:
    Name BareFunctionType

Name:
    N [CVRQualifiers] QualifiedName E
    LName

BareFunctionType:
    Type
    Type BareFunctionType

CVRQualifiers:
    [r] [V] [K]
--------------------
 */
private Demangle!(Symbol) parseCppMangledName(string man) pure
{
    string rem = man;
    Symbol sym;

    // expect "_Z"
    expect(startsWith(rem, "_Z"), "not a C++ mangled name", rem);
    rem = rem[2 .. $];

    if (startsWith(rem, "N"))
    {
        rem = rem[1 .. $];

        // Ignore CVR qualifiers.
        if (startsWith(rem, "r")) rem = rem[1 .. $];
        if (startsWith(rem, "V")) rem = rem[1 .. $];
        if (startsWith(rem, "K")) rem = rem[1 .. $];

        auto qname = parseQualifiedName(rem);
        rem = rem[qname.mangle.length .. $];
        sym = qname.content;

        expect(startsWith(rem, "E"), "'E' expected", rem);
        rem = rem[1 .. $];

        // BareFunctionType
        if (rem.length)
            throw new Exception("not implemented");
    }
    else
    {
        auto name = parseLName(rem);
        rem = rem[name.mangle.length .. $];
        sym = name.content;
    }

    return typeof(return)(man[0 .. $ - rem.length], sym);
}

unittest
{
    enum dem1 = parseCppMangledName("_ZN1C3fooE");
    static assert(dem1.mangle == "_ZN1C3fooE");
    static assert(toString(dem1.content) == "C.foo");

    alias throws!parseCppMangledName invalid;
    static assert(invalid("_D3std4math3sinFNaNbeZe")); // not C++
    static assert(invalid("")); // empty
}

// Returns true if the string man is expected to be a C++ mangled name.
private bool isCppMangledName(string man) pure nothrow
{
    return startsWith(man, "_Z");
}


